#ifndef COMMON_H
#define COMMON_H

#include "ObjectPool.h"

#include <iostream>
#include <cassert>

#include <thread>
#include <mutex>

#include <string.h>
#include <unordered_map>

#include <algorithm>

#include <sys/mman.h>
#include <atomic>

#include <chrono>
#include <ctime>

#define NFREE_LIST 208
#define MAX_BYTES 262144 // 256 * 1024
#define NPAGES 129       // 页数

#ifdef __linux__
#define PAGE_SHIFT 12 // 页面偏移
#elif _WIN32
#define PAGE_SHIFT 13
#endif

#ifdef _WIN64
using PAGE_ID = unsigned long long;
#elif _WIN32
using PAGE_ID = size_t;
#else
using PAGE_ID = unsigned long long;
#endif

using std::atomic;
using std::cout;
using std::endl;
using std::mutex;
using std::thread;
using std::unordered_map;

static void printMem(void **batch)
{
  printf("-------------mem-------------\n%p\n", *batch);
}

// 向堆中申请指定大小的内存
static void *systemAlloc(size_t nPage)
{
  // void* ptr = mmap(
  //   NULL,                   // 由内核选择地址
  //   size,                   // 分配大小
  //   PROT_READ | PROT_WRITE, // 可读可写
  //   MAP_PRIVATE | MAP_ANONYMOUS, // 私有匿名内存
  //   -1,                     // 无文件描述符
  //   0                       // 无偏移
  // );
  void *ptr = mmap(nullptr, nPage << PAGE_SHIFT, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

  assert(ptr);
  // 逻辑提交：mmap 返回的地址空间看似已分配。
  // 物理提交：实际物理页在首次访问内存时才由内核分配（触发缺页异常）。
  memset(ptr, 0, nPage << PAGE_SHIFT);

  return ptr;
}

static void systemFree(void *obj, size_t objSize)
{
  int ret = munmap(obj, objSize);
  assert(ret == 0);
}

// 二级指针，内存中指向下一块内存的地址
static void *&nextObj(void *obj)
{
  return *(void **)obj;
}

static int min(int lhs, int rhs)
{
  return lhs < rhs ? lhs : rhs;
}

class FreeList
{
public:
  // 向自由链表中添加空间
  void push(void *obj)
  {
    assert(obj);

    nextObj(obj) = _freeList;
    _freeList = obj;

    _size++;
  }

  void pushRange(void *start, void *end, size_t batchNum)
  {
    nextObj(end) = _freeList;
    _freeList = start;

    _size += batchNum;
  }

  // 申请内存
  void *pop()
  {
    assert(_freeList);

    void *obj = _freeList;
    _freeList = nextObj(obj);

    _size--;
    return obj;
  }

  void popRange(void *&start, void *&end, size_t batchNum)
  {
    assert(batchNum >= maxFetchSize());
    assert(_freeList);

    start = _freeList;
    end = start;

    size_t k = 1;
    while (k++ < batchNum)
    {
      end = nextObj(end);
    }

    _freeList = nextObj(end);
    nextObj(end) = nullptr;

    _size -= batchNum;
  }

  bool empty()
  {
    return _freeList == nullptr;
  }

  int &maxFetchSize()
  {
    return _maxFetchSize;
  }

  size_t size()
  {
    return _size;
  }

private:
  // 管理单个桶的自由链表
  void *_freeList = nullptr;
  int _maxFetchSize = 1;
  size_t _size = 0;
};

class SizeClass
{
  // 整体控制在最多10%左右的内碎片浪费
  // [1,128]					8byte对齐	    freelist[0,16)
  // [128+1,1024]				16byte对齐	    freelist[16,72)
  // [1024+1,8*1024]			128byte对齐	    freelist[72,128)
  // [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
  // [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)
public:
  static size_t maxFetchSize(size_t size)
  {
    int num = MAX_BYTES / size;
    if (num < 2)
      return 2;
    else if (num > 512)
      return 512;
  }

  // 获取多少页span
  static size_t maxNPage(size_t size)
  {
    size_t nPage = size >> PAGE_SHIFT;
    if (nPage < 1)
      return 1;
    return nPage;
  }

  static size_t roundUp(size_t size)
  {
    if (size <= 128)
    {
      return _roundUp(size, 8);
    }
    else if (size <= 1024)
    {
      return _roundUp(size, 16);
    }
    else if (size <= 8 * 1024)
    {
      return _roundUp(size, 128);
    }
    else if (size <= 64 * 1024)
    {
      return _roundUp(size, 1024);
    }
    else if (size <= 256 * 1024)
    {
      return _roundUp(size, 4 * 1024);
    }
    else if (size > 256 * 1024)
    {
      return _roundUp(size, 4 * 1024);
    }
    else
    {
      assert(false);
      return -1;
    }
  }

  static size_t _roundUp(size_t size, size_t align)
  {
    return (size + align - 1) & ~(align - 1);
  }

  static size_t _index(size_t size, size_t align_shift)
  {
    return ((size + (1 << align_shift) - 1) >> align_shift) - 1;
  }

  static size_t index(size_t size)
  {
    constexpr static int bucket[] = {16, 56, 56, 56};
    if (size <= 128)
      return _index(size, 3);
    else if (size <= 1024)
      return _index(size - 128, 4) + bucket[0];
    else if (size <= 8 * 1024)
      return _index(size - 1024, 7) + bucket[0] + bucket[1];
    else if (size <= 64 * 1024)
      return _index(size - 8 * 1024, 10) + bucket[0] + bucket[1] + bucket[2];
    else if (size <= 256 * 1024)
      return _index(size - 64 * 1024, 13) + bucket[0] + bucket[1] + bucket[2] + bucket[3];
    else
      assert(false);

    return -1;
  }
};

// 管理多个连续页大块内存跨度结构
struct Span
{
  PAGE_ID _page_id = 0; // 大块内存从哪个页开始
  int _n = 0;           // 页的数量

  Span *_next = nullptr;
  Span *_pre = nullptr;

  int _use_count = 0;        // 被分配到thread cache中的数量
  void *_freeList = nullptr; // 切好的小块内存

  bool _isUse = true; // 当前span是否正在使用
  size_t _batchSize = 0;
};

class SpanList
{
public:
  SpanList()
  {
    _head = new Span;
    _head->_next = _head;
    _head->_pre = _head;
  }

  bool empty()
  {
    return _head->_next == _head;
  }

  Span *begin()
  {
    return _head->_next;
  }

  Span *end()
  {
    return _head;
  }

  Span *pop()
  {
    Span *span = _head->_next;
    erase(span);
    return span;
  }

  void erase(Span *span)
  {
    assert(span);
    assert(span->_next);
    assert(span->_pre);
    Span *pre = span->_pre;
    Span *next = span->_next;

    pre->_next = next;
    next->_pre = pre;
  }

  void pushFront(Span *span)
  {
    Span *tmp = _head->_next;
    _head->_next = span;
    span->_next = tmp;
    tmp->_pre = span;
    span->_pre = _head;
  }

private:
  Span *_head;

public:
  mutex _mtx;
};

#endif
